package main

import "fmt"

// 第一问就是给一个i和j，找出身边四个方向里为0的所有格子。

// 给一个二维matrix，-1代表墙，0代表路。问给定一个起点坐标为0，是否能到达所有的0。

func allVisited(matrix [][]int, i, j int) bool {
	visited := make([][]bool, len(matrix))
	for i := 0; i < len(matrix); i++ {
		visited[i] = make([]bool, len(matrix[i]))
	}
	matrixDFS(&visited, matrix, i, j)

	// fmt.Println(visited)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if matrix[i][j] == 0 && visited[i][j] != true {
				return false
			}
		}
	}
	return true
}

func matrixDFS(visited *[][]bool, matrix [][]int, i, j int) {
	// fmt.Printf("%v, %v\n", i, j)
	if (i < 0 || i >= len(matrix)) ||
		j < 0 || j >= len(matrix[0]) {
		return
	} else if matrix[i][j] == -1 {
		return
	} else if (*visited)[i][j] == true {
		return
	}
	(*visited)[i][j] = true
	matrixDFS(visited, matrix, i-1, j)
	matrixDFS(visited, matrix, i+1, j)
	matrixDFS(visited, matrix, i, j-1)
	matrixDFS(visited, matrix, i, j+1)
	return
}

// board3 中1代表钻石，给出起点和终点，问有没有一条不走回头路的路线，能从起点走到终点，并拿走所有的钻石，给出所有的最短路径。

// board3 = [
//     [  1,  0,  0, 0, 0 ],
//     [  0, -1, -1, 0, 0 ],
//     [  0, -1,  0, 1, 0 ],
//     [ -1,  0,  0, 0, 0 ],
//     [  0,  1, -1, 0, 0 ],
//     [  0,  0,  0, 0, 0 ],
// ]

// treasure(board3, (5, 0), (0, 4)) -> None

// treasure(board3, (5, 2), (2, 0)) ->
//   [(5, 2), (5, 1), (4, 1), (3, 1), (3, 2), (2, 2), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0)]
//   Or
//   [(5, 2), (5, 1), (4, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0)]

// treasure(board3, (0, 0), (4, 1)) ->
//   [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (3, 1), (4, 1)]
//   Or
//   [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (4, 1)]

func findTreasure(board [][]int, start, end [2]int) [][][2]int {
	res := [][][2]int{}
	treasureCnt := 0
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if board[i][j] == 1 {
				treasureCnt++
			}
		}
	}

	// one path
	path := [][2]int{}

	findTreasureDFS(&board, start, end, treasureCnt, path, &res)

	return res
}

// func shortestPath(matrix [][]int, start, end [2]int) [][][2]int {
// 	res := [][][2]int{}
// 	treasureNum := 0
// 	for i := 0; i < len(matrix); i++ {
// 		for j := 0; j < len(matrix[0]); j++ {
// 			if matrix[i][j] == 1 {
// 				treasureNum++
// 			}
// 		}
// 	}
// 	path := [][2]int{}
// 	findTreasureDFS(&matrix, start[0], start[1], end, treasureNum, path, &res)

// 	shortest := 1000
// 	for _, path := range res {
// 		// fmt.Println(path)

// 		if len(path) < shortest {
// 			shortest = len(path)
// 		}
// 	}
// 	for _, path := range res {
// 		if len(path) == shortest {
// 			fmt.Println(path)
// 		}
// 	}
// 	return res
// }

func findTreasureDFS(board *[][]int, start, end [2]int, remaining int, path [][2]int, res *[][][2]int) {
	i := start[0]
	j := start[1]
	if i < 0 || i >= len(*board) ||
		j < 0 || j >= len((*board)[0]) ||
		(*board)[i][j] == -1 || (*board)[i][j] == -2 {
		// no way to go
		return
	}

	temp := (*board)[i][j]

	if (*board)[i][j] == 1 {
		remaining -= 1
	}

	path = append(path, [2]int{i, j})

	if start == end && remaining == 0 {
		fmt.Println(path)
		return
	}
	// visited
	(*board)[i][j] = -2
	findTreasureDFS(board, [2]int{i - 1, j}, end, remaining, path, res)
	findTreasureDFS(board, [2]int{i + 1, j}, end, remaining, path, res)
	findTreasureDFS(board, [2]int{i, j - 1}, end, remaining, path, res)
	findTreasureDFS(board, [2]int{i, j + 1}, end, remaining, path, res)
	(*board)[i][j] = temp
	return
	// if i < 0 || i >= len(*matrix) ||
	// 	j < 0 || j >= len((*matrix)[0]) ||
	// 	(*matrix)[i][j] == -1 || // block
	// 	(*matrix)[i][j] == -2 { // visited
	// 	return
	// }
	// temp := (*matrix)[i][j]

	// if (*matrix)[i][j] == 1 {
	// 	// find one
	// 	remaining -= 1
	// }
	// path = append(path, [2]int{i, j})
	// if i == end[0] && j == end[1] && remaining == 0 {
	// 	// found all and at the end
	// 	// fmt.Println(path)
	// 	one := [][2]int{}
	// 	for _, ele := range path {
	// 		one = append(one, ele)
	// 	}
	// 	// fmt.Println(one)
	// 	*res = append(*res, one)
	// 	(*matrix)[i][j] = temp
	// 	return
	// }
	// (*matrix)[i][j] = -2 // visited
	// // else traverse
	// findTreasureDFS(matrix, i-1, j, end, remaining, path, res)
	// findTreasureDFS(matrix, i+1, j, end, remaining, path, res)
	// findTreasureDFS(matrix, i, j-1, end, remaining, path, res)
	// findTreasureDFS(matrix, i, j+1, end, remaining, path, res)
	// (*matrix)[i][j] = temp
	// return
}

// func RemoveLast(s [][2]int) [][2]int {
// 	ret := make([][2]int, 0)
// 	for i := 0; i < len(s)-1; i++ {
// 		ret = append(ret, [2]int{s[i][0], s[i][1]})
// 	}
// 	// ret = append(ret, s[:len(s)]...)
// 	return ret
// }

func main() {
	input := [][]int{
		[]int{0, 0, 0, -1, 0},
		[]int{0, -1, -1, -1, -1},
		[]int{0, -1, -1, 0, 0},
		[]int{-1, 0, 0, 0, 0},
		[]int{0, 0, -1, 0, 0},
		[]int{0, 0, -1, 0, 0},
	}
	// board3 = [
	//     [  1,  0,  0, 0, 0 ],
	//     [  0, -1, -1, 0, 0 ],
	//     [  0, -1,  0, 1, 0 ],
	//     [ -1,  0,  0, 0, 0 ],
	//     [  0,  1, -1, 0, 0 ],
	//     [  0,  0,  0, 0, 0 ],
	// ]
	fmt.Println(allVisited(input, 0, 0))
	input2 := [][]int{
		[]int{1, 0, 0, 0, 0},
		[]int{0, -1, -1, 0, 0},
		[]int{0, -1, 0, 1, 0},
		[]int{-1, 0, 0, 0, 0},
		[]int{0, 1, -1, 0, 0},
		[]int{0, 0, 0, 0, 0},
	}
	// path := [][2]int{
	// 	[2]int{1, 2},
	// 	[2]int{2, 4},
	// }
	// path = RemoveLast(path)
	// input2 := [][]int{
	// 	[]int{1, 0, 0, 0, 0},
	// 	[]int{0, -1, -1, 0, 0},
	// }
	findTreasure(input2, [2]int{5, 2}, [2]int{2, 0})
}
